/**
 * <p>Title: Cell Class</p>
 * <p>Description: CS 343 Project</p>
 * @author Quintin Stolpe
 * @email quintin.stolpe@my.uwrf.edu
 * @date Dec 3 2012
*/

package maze;

import java.util.Random;
import java.util.Vector;

public class Maze
{

	private boolean mirror = false;

	private int height = 7;//19;//9;
	private int width = 7;//23;//11;

	public Cell cells[][] = null;

	private Random random = new Random();

	private static final int NORTH = 0;
	private static final int EAST = 1;
	private static final int SOUTH = 2;
	private static final int WEST = 3;

	public static final int EMPTY_SQUARE = 0;
	public static final int WALL = 1;
	public static final int PELLET = 2;
	public Graph myGraph = null;
	
	/**
	 * Maze constructor
	 */
	public Maze(int w, int h)
	{
		width = w;
		height = h;
		cells = new Cell[width][height];
		

		for (int x = 0; x < cells.length; x++)
		{
			for (int y = 0; y < cells[x].length; y++)
			{
				cells[x][y] = new Cell(x, y);
				if (x == 0
					|| x == cells.length - 1
					|| y == 0
					|| y == cells[x].length - 1)
				{
					cells[x][y].visited = true;
				}
			}
		}

		generateMaze(1, 1);
		
		doDeadEndRemoval();

	}
	public void generateMaze(int x, int y)
	{
		cells[x][y].visited = true;
		if (mirror)
		{
			cells[x][cells[x].length - y - 1].visited = true;
		}

		int outDirection = random.nextInt(4);

		int outX;
		int outY;

		for (int i = 0; i < 4; i++)
		{
			outDirection = (outDirection + i) % 4;

			outX = newX(x, outDirection);
			outY = newY(y, outDirection);
			if (!cells[outX][outY].visited)
			{
				cells[x][y].walls[outDirection] = false;
				if (mirror)
				{

					cells[x][cells[x].length
						- y
						- 1].walls[mirrorDirection(outDirection)] =
						false;
				}
				generateMaze(outX, outY, reverseDirection(outDirection));
			}
		}

	}
	public void generateMaze(int x, int y, int inDirection)
	{
		cells[x][y].visited = true;
		if (mirror)
		{
			cells[x][cells[x].length - y - 1].visited = true;
		}

		cells[x][y].walls[inDirection] = false;
		if (mirror)
		{
			cells[x][cells[x].length
				- y
				- 1].walls[mirrorDirection(inDirection)] =
				false;
		}
		int outDirection = random.nextInt(4);

		int outX;
		int outY;

		for (int i = 0; i < 4; i++)
		{
			outDirection = (outDirection + i) % 4;

			outX = newX(x, outDirection);
			outY = newY(y, outDirection);
			int divisor = 1;
			if (mirror)
			{
				divisor = 2;
			}
			if (!cells[outX][outY].visited
				&& outY <= cells[x].length / divisor)
			{
				cells[x][y].walls[outDirection] = false;

				if (mirror)
				{
					cells[x][cells[x].length
						- y
						- 1].walls[mirrorDirection(outDirection)] =
						false;
				}
				generateMaze(outX, outY, reverseDirection(outDirection));
			}
		}

	}

	private void doDeadEndRemoval()
	{
		int x, y;
		Vector deadEndCells = new Vector();

		// put all dead ends into a Vector
		for (x = 0; x < cells.length; x++)
		{
			for (y = 0; y < cells[x].length; y++)
			{
				if (cells[x][y].wallCount() == 3)
				{
					deadEndCells.add(cells[x][y]);

				}
			}
		}

		while (deadEndCells.elements().hasMoreElements())
		{
			Cell currentCell = (Cell) (deadEndCells.elements().nextElement());
			System.out.println(
				"Removing " + currentCell.x + "," + currentCell.y);
			Cell neighborCell = null;

			deadEndCells.remove(currentCell);

			neighborCell = new Cell(currentCell.x - 1, currentCell.y);

			if (deadEndCells.contains(neighborCell))
			{
				removeWall(currentCell, neighborCell);
				deadEndCells.remove(neighborCell);
			}
			else
			{
				neighborCell.x = currentCell.x + 1;

				if (deadEndCells.contains(neighborCell))
				{
					removeWall(
						currentCell,
						cells[neighborCell.x][neighborCell.y]);
					deadEndCells.remove(neighborCell);

				}
				else
				{
					neighborCell.x = currentCell.x;
					neighborCell.y = currentCell.y - 1;

					if (deadEndCells.contains(neighborCell))
					{
						removeWall(
							currentCell,
							cells[neighborCell.x][neighborCell.y]);
						deadEndCells.remove(neighborCell);

					}
					else
					{
						neighborCell.y = currentCell.y + 1;

						if (deadEndCells.contains(neighborCell))
						{
							removeWall(
								currentCell,
								cells[neighborCell.x][neighborCell.y]);
							deadEndCells.remove(neighborCell);

						}
						else // no neighbors
							{
							// the remove call should never work
							if(deadEndCells.remove(fixDeadEnd(currentCell)))
							{
								System.out.println("This should never happen");
							} 
						}
					}

				}

			}

		deadEndCells.remove(currentCell);
		
		}
		
		System.out.println("Dead ends remaining:"+deadEndCells.size());

	}

	private Cell fixDeadEnd(Cell aCell)
	{
		int outDir = 0;
		for (int i = 0; i < aCell.walls.length; i++)
		{
			if (!aCell.walls[i])
			{
				outDir = reverseDirection(i);
			}
		}

		Cell testCell = cells[newX(aCell.x, outDir)][newY(aCell.y, outDir)];
		if (testCell.wallCount() != 4)
		{
			removeWall(aCell, testCell);
		}
		else
		{
			outDir = (outDir + 1) % 4;
			testCell = cells[newX(aCell.x, outDir)][newY(aCell.y, outDir)];
			if (testCell.wallCount() != 4)
			{
				removeWall(aCell, testCell);
			}
			else
			{
				outDir = (outDir + 2) % 4;
				testCell = cells[newX(aCell.x, outDir)][newY(aCell.y, outDir)];
				if (testCell.wallCount() != 4)
				{
					removeWall(aCell, testCell);
				}
				else
				{
					System.out.println(
						"problem removing " + aCell.x + "," + aCell.y);
				}
			}

		}
		return testCell;

	}

	private void removeWall(Cell cellA, Cell cellB)
	{
		int dX = cellA.x - cellB.x;
		int dY = cellA.y - cellB.y;

		System.out.println(
			"maze.removeWall(("
				+ cellA.x
				+ ","
				+ cellA.y
				+ "),("
				+ cellB.x
				+ ","
				+ cellB.y
				+ "))");
		if (dX == 1)
		{
			cellA.walls[WEST] = false;
			cellB.walls[EAST] = false;

		}
		else if (dX == -1)
		{
			cellA.walls[EAST] = false;
			cellB.walls[WEST] = false;

		}
		else if (dY == 1)
		{
			cellA.walls[NORTH] = false;
			cellB.walls[SOUTH] = false;
		}
		else if (dY == -1)
		{
			cellA.walls[SOUTH] = false;
			cellB.walls[NORTH] = false;
		}
		else
		{
			System.out.println(
				"Problem in maze.removeWall(("
					+ cellA.x
					+ ","
					+ cellA.y
					+ "),("
					+ cellB.x
					+ ","
					+ cellB.y
					+ "))");
		}
	}
	
	public int[][] generateMazeArray()
	{
		int[][] array = new int[width * 2 + 1][height * 2 + 1];

		int x, y;

		// convert from cells to blocky array
		for (x = 0; x < cells.length; x++)
		{
			for (y = 0; y < cells[x].length; y++)
			{
				// top row
				if (cells[x][y].walls[NORTH] || cells[x][y].walls[WEST])
				{
					array[x * 2][y * 2] = WALL;
				}

				if (cells[x][y].walls[NORTH])
				{
					array[x * 2 + 1][y * 2] = WALL;
				}

				if (cells[x][y].walls[NORTH] || cells[x][y].walls[EAST])
				{
					array[x * 2 + 2][y * 2] = WALL;
				}

				// middle row
				if (cells[x][y].walls[WEST])
				{
					array[x * 2][y * 2 + 1] = WALL;
				}

				// always open - ok, not on borders
				array[x * 2 + 1][y * 2 + 1] = EMPTY_SQUARE;

				if (cells[x][y].walls[EAST])
				{
					array[x * 2 + 2][y * 2 + 1] = WALL;
				}

				// bottom row

				if (cells[x][y].walls[SOUTH] || cells[x][y].walls[WEST])
				{
					array[x * 2][y * 2 + 2] = WALL;
				}

				if (cells[x][y].walls[SOUTH])
				{
					array[x * 2 + 1][y * 2 + 2] = WALL;
				}

				if (cells[x][y].walls[SOUTH] || cells[x][y].walls[EAST])
				{
					array[x * 2 + 2][y * 2 + 2] = WALL;
				}

			}
		}

		int[][] newArray = new int[array.length - 4][array[0].length - 4];
	
		// get rid of giant borders
		for (x = 2; x < array.length - 2; x++)
		{
			for (y = 2; y < array[x].length - 2; y++)
			{
				newArray[x - 2][y - 2] = array[x][y];

				if (array[x][y] == WALL)
				{
					newArray[x - 2][y - 2] = WALL;
					System.out.print("X");
				}
				else
				{
					newArray[x - 2][y - 2] = EMPTY_SQUARE;
					System.out.print(" ");
				}
				if (array[x-1][y-1] == EMPTY_SQUARE &&
					array[x-1][y] == EMPTY_SQUARE &&
					array[x-1][y+1] == EMPTY_SQUARE &&
					array[x][y-1] == EMPTY_SQUARE &&
					array[x][y] == EMPTY_SQUARE &&
					array[x][y+1] == EMPTY_SQUARE &&
					array[x+1][y-1] == EMPTY_SQUARE &&
					array[x+1][y] == EMPTY_SQUARE &&
					array[x+1][y+1] == EMPTY_SQUARE)
				{	
					newArray[x - 2][y - 2] = WALL;
					System.out.print("O");
				}
					
				
			}
			System.out.println("");
		}

		// random wall removal
		for (x = 1; x < newArray.length - 2; x++)
		{
			for (y = 1; y < newArray[x].length - 2; y++)
			{
				if (newArray[x][y] == WALL)
				{
					int testVal =
						newArray[x][y
							- 1]
							+ 2 * newArray[x
							+ 1][y]
							+ 4 * newArray[x][y
							+ 1]
							+ 8 * newArray[x
							- 1][y];
					if (testVal == 5 || testVal == 10)
					{
						// wall removal
						if (random.nextInt(10) < 0)
						{
							newArray[x][y] = EMPTY_SQUARE;
							
							newArray[x][newArray[x].length - y - 1] =
								EMPTY_SQUARE;
						}
					}
				}
			}
		}

		myGraph = new Graph();
		myGraph.makeGraph(newArray);
		
		// INSERT PELLETS	
		for (x = 0; x < newArray.length; x++)
		{
			for (y = 0; y < newArray[x].length; y++)
			{
				if (newArray[x][y] != WALL)
				{
					newArray[x][y] = PELLET;
				}
			}
		}

		return newArray;

	}
	private int mirrorDirection(int dir)
	{
		if (dir == NORTH)
			return SOUTH;
		if (dir == SOUTH)
			return NORTH;
		return dir;
	}
	private int newX(int x, int direction)
	{
		if (direction == EAST)
		{
			return x + 1;
		}
		if (direction == WEST)
		{
			return x - 1;
		}
		return x;
	}
	private int newY(int y, int direction)
	{
		if (direction == SOUTH)
		{
			return y + 1;
		}
		if (direction == NORTH)
		{
			return y - 1;
		}
		return y;
	}
	private int reverseDirection(int dir)
	{
		if (dir == NORTH)
			return SOUTH;
		if (dir == SOUTH)
			return NORTH;
		if (dir == EAST)
			return WEST;
		return EAST;
	}
}
